import org.junit.Test;

/**
 * @author yunzhang
 * 
 */
public class BinarySearcher {

	/**
	 * Classic binary search algorithm
	 * 
	 * @param arr
	 * @param t
	 * @return
	 */
	public int binarySearch(int[] arr, int t) {
		if (arr == null || arr.length == 0)
			return -1;
		return binarySearch(arr, t, 0, arr.length - 1);
	}

	private int binarySearch(int[] arr, int t, int l, int u) {
		if (l > u)
			return -1;

		int m = (l + u) / 2;
		if (arr[m] == t)
			return m;
		else if (arr[m] > t)
			return binarySearch(arr, t, l, m - 1);
		else
			return binarySearch(arr, t, m + 1, u);
	}

	/**
	 * Modified version of binary search. Given a sorted array and keyword, the
	 * algo returns the position of the first instance of that keyword.
	 * 
	 * @param arr
	 * @param t
	 * @return
	 */
	public int binarySearch2(int[] arr, int t) {
		if (arr == null || arr.length == 0)
			return -1;

		return binarySearch2(arr, t, 0, arr.length - 1);
	}

	private int binarySearch2(int[] arr, int t, int l, int u) {
		if (l > u)
			return -1;

		int m = (l + u) / 2;
		if (arr[m] == t) {
			int cs = binarySearch2(arr, t, l, m - 1);
			return (cs != -1) ? cs : m;
		} else if (arr[m] > t)
			return binarySearch2(arr, t, l, m - 1);
		else
			return binarySearch2(arr, t, m + 1, u);
	}

	@Test
	public void binarySearhTest() {
		int[] array = new int[] { 1, 2, 2, 3, 4, 5, 6, 7, 7, 7, 8, 9, 10 };

		BinarySearcher bs = new BinarySearcher();
		System.out.println(bs.binarySearch(array, 7));
	}

	@Test
	public void binarySearchTest() {
		int[] array = new int[] { 1, 2, 2, 3, 4, 5, 6, 7, 7, 7, 8, 9, 10 };
		BinarySearcher bs = new BinarySearcher();
		System.out.println(bs.binarySearch2(array, 7));

		array = new int[] { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 };
		System.out.println(bs.binarySearch2(array, 2));
	}
}
